package com.lw.leetcode.other.b;

/**
 * Created with IntelliJ IDEA.
 * 204. 计数质数
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/16 10:25
 */
public class CountPrimes {

    public int countPrimes(int n) {
        if (n < 2) {
            return 0;
        }
        if (n < 4) {
            return n - 2;
        }
        boolean[] a = new boolean[n];
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (!a[i]) {
                count++;
                for (int j = 2; j < n; j++) {
                    int i1 = j * i;
                    if (i1 < n) {
                        a[j * i] = true;
                    } else {
                        break;
                    }
                }
            }
        }
        return count;
    }

}
